package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.List;

/* 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。 */
public class lc131 {
    class Solution {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        
        public List<List<String>> partition(String s) {
            backtracking(s, 0);
            return res;
        }
        public void backtracking(String s, int index){
            if (index>=s.length()) {
                // 终止条件,深度大于字符串长度,终止递归
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = index; i < s.length(); i++) {
                if (isPalindrome(s, index, i)) {
                    String str = s.substring(index, i+1);
                    path.add(str);
                    backtracking(s, i+1);
                    path.removeLast();
                }
            }
        }
        // 采用双指针法判断是否是回文串
        public boolean isPalindrome(String s, int start, int end){
            for (int i = start, j = end; i < j; i++, j--) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }
            }
            return true;
        }
    }
}
